package com.Questions.DFS;


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 课程表2
 */
public class leetcode210 {
    List<List<Integer>> edges;
    int[] indeg;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<List<Integer>>();
        for (int i = 0; i < numCourses; ++i) {
            edges.add(new ArrayList<Integer>());
        }
        indeg = new int[numCourses];// 存储一个点的入度
        for (int[] info : prerequisites) {
            edges.get(info[1]).add(info[0]);
            ++indeg[info[0]];
        }

        Queue<Integer> queue = new LinkedList<Integer>();
        for (int i = 0; i < numCourses; ++i) {// 初始化 将所有结点中
            if (indeg[i] == 0) {//入度为0 的结点 放入队列
                queue.offer(i);
            }
        }
        List<Integer> vis=new ArrayList<>();
        int visited = 0;
        while (!queue.isEmpty()) {

            ++visited;
            int u = queue.poll();
            vis.add(u);
            for (int v: edges.get(u)) {
                --indeg[v];
                if (indeg[v] == 0) {
                    queue.offer(v);
                }
            }
        }
        if(visited!=numCourses){
            return new int[0];
        }else{
            int[] ans=new int[vis.size()];
            for(int i=0;i<vis.size();++i){
                ans[i]=vis.get(i);
            }
            return ans;
        }
    }
}
